package array;

/**
 * @Classname : NextPermutation
 * @Description : 31. 下一个排列
 * https://leetcode.cn/problems/next-permutation/
 * @Author : chentianyu
 * @Date 2023/3/7 00:13
 */


public class NextPermutation {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0) {  // 从后向前遍历，查找第一次出现 nums[i] < nums[i + 1]的位置i
            if (nums[i] < nums[i + 1]) break;
            i--;
        }

        if (i >= 0) {  // 若存在大于nums[i]的整数
            int m = i + 1;  // 则从 i + 1 向后遍历，查找大于nums[i]的最小整数的位置m
            for (int j = i + 2; j < n; j++) {
                if (nums[j] > nums[i] && nums[j] <= nums[m]) m = j;  // 注意：必须使用 <= 才能保证后续交换位置后单调性不变
            }
            swap(nums, i, m);  // 交换二者位置
        }

        // 若存在大于nums[i]的整数，则将位置i之后的元素升序排列
        // 若不存在，则将整个数组升序排列
        reverse(nums, i + 1, n - 1);
    }

    // 数组指定位置元素交换
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    // 数组指定降序排列范围，通过双指针实现升序排列
    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            swap(nums, l++, r--);
        }
    }
}
